import java.util.*;
public class Day15 {
    public static void main(String[] args) {

    }
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map = new HashMap<>();
        //1.统一异位词
        for(String s:strs) {
            char[] tmp = s.toCharArray();
            Arrays.sort(tmp);
            String key = new String(tmp);

            if(!map.containsKey(key)) {
                map.put(key,new ArrayList());
            }
            map.get(key).add(s);
        }
        return new ArrayList(map.values());
    }
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];//以i为结尾的所有子串，并且差值是正数的最长子串长度
        int[] g = new int[n];
        for(int i=0;i<n;i++) {
            f[i]=1;
            g[i]=1;
        }
        int ret = 1;//记录返回值
        for(int i=1;i<n;i++) {
            for(int j=i-1;j>=0;j--) {
                if(nums[i] - nums[j] > 0) {
                    g[i] = Math.max(g[i],f[j]+1);
                }else if(nums[i] - nums[j] < 0) {
                    f[i] = Math.max(f[i],g[j]+1);
                }
            }
            ret = Math.max(Math.max(f[i],g[i]),ret);
        }
        return ret;
    }

}
